Vous travaillez dans une entreprise en tant que chef du centre d'opérations de sécurité, l'équipe d'expert.e.s en cybersécurité qui a pour charge de surveillée en continu, à détecter et à répondre aux incidents informatiques pouvant avoir un lien avec la sécurité.
Vous avez pour mission de déployer un ensemble de capteurs de détection sur le réseau de cette entreprise.

Voici un tableau synthétisant les différentes zones du réseau de l'entreprise :

Voici un tableau résumant les 10 types de capteurs que vous pouvez acheter pour l'entreprise ; chacun de ces capteurs peut couvrir quelques zones du réseau, a un coût en euro et possède un degré de fiabilité en pourcentage.

L'entreprise vous impose de couvrir les 12 zones du réseau avec un budget maximal de 35000€ en cherchant à maximiser la fiabilité totale tout en minimisant le coût et le nombre de capteurs afin de réduire les risques et les coûts de maintenance.

Ce problème s'appelle le Set Cover Problem ; c'est un problème dont on ne connaît pas dans le cas général d'algorithme qui permet de trouver efficacement une solution optimale. La recherche exhaustive conduit à tester les $2^n$ combinaisons possibles dans le cas où $n$ capteurs sont considérés.
Dès lors, utiliser une méthode gloutonne est ici utile, même si elle ne garanti pas de trouver la solution optimale.

La démarche gloutonne à appliquer consiste à :

1. Classer les capteurs suivant le rapport $\dfrac{\text{nombre de zones couvertes}\times\text{fiabilité}}{\text{coût}}$.

2. À chaque itération, regarder si le capteur peut couvrir une zone non encore couverte sans dépassement des coûts.

3. Arrêter quand tout le budget est dépensé ou toutes les zones couvertes ou tous les capteurs étudiés.

Voici les données des deux tableaux précédents partiellement implémentées en Python :

zones = [
    "DMZ", "LAN", "VLAN-Dev", "VLAN-Prod", "VLAN-Test",
    "WAN", "Cloud-Pub", "Cloud-Priv", "IoT", "Guest", "DB", "HR"
]

capteurs = [
    {"id": "C1", "zones": ["DMZ", "LAN", "WAN"], "cout": 8000, "fiabilite": 95},
    {"id": "C2", "zones": ["VLAN-Dev", "VLAN-Test", "Cloud-Pub"], "cout": 6000, "fiabilite": 90},
    {"id": "C3", "zones": ["VLAN-Prod", "DB", "Cloud-Priv"], "cout": 10000, "fiabilite": 98},
    {"id": "C4", "zones": ["DMZ", "Cloud-Pub", "WAN"], "cout": 9000, "fiabilite": 97},
    {"id": "C5", "zones": ["IoT", "Guest", "LAN"], "cout": 4000, "fiabilite": 85},
    {"id": "C6", "zones": ["DB", "HR", "Cloud-Priv"], "cout": 7000, "fiabilite": 92},
    {"id": "C7", "zones": ["VLAN-Dev", "VLAN-Prod", "VLAN-Test"], "cout": 5000, "fiabilite": 88},
    {"id": "C8", "zones": ["WAN", "Cloud-Pub", "Cloud-Priv"], "cout": 12000, "fiabilite": 96},
    {"id": "C9", "zones": ["HR", "LAN", "Guest"], "cout": 3000, "fiabilite": 80},
    {"id": "C10", "zones": ["IoT", "DMZ", "VLAN-Prod"], "cout": 11000, "fiabilite": 94},
]

1. Au cours de la recherche d'une solution, il sera utile de pouvoir connaître les éléments communs à deux listes, celle des zones non encore couvertes et celle des zones couverte par un capteur donné.
   La liste obtenue sera sans doublon et ses éléments dans l'ordre d'apparition dans la première des deux listes.

   Proposer une fonction intersection qui prend en paramètre paramètre deux listes liste1 et liste2 et qui renvoie la liste formée des éléments appartenant à ces deux listes, sans doublon, avec pour ordre celui d'apparition dans la première liste.

   Tester la fonction créée à l'aide de la fonction tests_intersection suivante :

   def tests_intersection():
       assert intersection([1, 3, 2, 1, 4, 5], []) == [], "erreur dans le cas d'une liste vide"
       assert intersection([], [1, 3, 2, 1, 4, 5]) == [], "erreur dans le cas d'une liste vide"
       assert intersection([5], [2, 3, 5, 6]) ==  [5], "erreur dans le cas d'une première liste incluse dans la seconde"
       assert intersection([2, 3, 5, 6], [2, 5]) ==  [2, 5], "erreur dans le cas d'une seconde liste incluse dans la première"
       assert intersection([1, 3, 4, 1, 2, 5], [1, 2, 3]) ==  [1, 3, 2], "erreur sur l'ordre du renvoi"
       assert intersection([1, 3, 2, 1, 4, 5], [7, 8, 9]) ==  [], "erreur dans le cas de listes non vides disjointes"
       assert intersection([0, 3, 4, 9, 1, 4, 5], [1, 4, 2, 1, 7, 8, 4]) ==  [4, 1], "erreur dans la gestion des doublons"
       print("tests réussis !")

2. Au cours de la recherche d'une solution, il sera utile de pouvoir connaître la différence entre deux listes, celle des zones non encore couvertes et celle des zones couverte par un capteur donné pour savoir ce qu'il restera à couvrir finalement.

   Proposer une fonction différence qui prend en paramètre paramètre deux listes liste1 et liste2 et qui renvoie la liste formée des éléments de la liste liste1 qui n'appartiennent pas à liste2. On ne prend pas en compte le nombre de fois où chaque élément présent apparaît dans les listes. Les éléments de la liste renvoyée sont dans l'ordre de leur apparition dans la première liste donnée en argument.

   Tester la fonction créée.

3. Pour essayer d'approcher de l'optimisation recherchée, il peut être judicieux de rajouter à chaque dictionnaire (capteur) de la liste capteurs une association de clé "ratio" et de valeur le résultat du produit du nombre de zones couvertes par la fiabilité du capteur, le tout divisé par le coût de ce capteur.

   Proposer une fonction rajouter_ratio qui prend en paramètre paramètre une liste liste_dico de type comme celle capteurs, qui rajoute à chacun des dictionnaire de cette liste l'association "ratio": valeur précéisée ci-dessus puis qui renvoie la liste de dictionnaires modifiés.

   Tester la fonction créée.

4. Compléter le script ci-dessous afin que la liste capteurs ait ses dictionnaires augmentés de l'association de clé "ratio" puis quelle soit triée par ordre décroissant de ces ratios.
   Attention ! Il est sous-entendu ici que capteurs corresponde à la liste mentionnée précédemment.

   # rajout de l'association de clé "ratio"
   capteurs = ...
   
   # tri par ordre croissant du "ratio"
   capteurs = sorted(capteurs, key=lambda dico: dico[...])
   # pour obtenir l'ordre décroissant :
   capteurs....

5. Compléter le script ci-dessous afin que la liste capteurs ait ses dictionnaires augmentés de l'association de clé "ratio" puis quelle soit triée par ordre décroissant de ces ratios.
   Attention ! Il est sous-entendu ici que capteurs corresponde à la liste mentionnée précédemment.

   # ===== DONNÉES zones ET capteurs À RAJOUTER ICI =====
       
   # ===== FONCTIONS AUXILIAIRES intersection, différence ET rajouter_ratio À RAJOUTER ICI =====
   
   # ===== TRI PAR ORDRE DÉCROISSANT DES RATIOS DE capteurs À RAJOUTER ICI =====
   
   # ===== NOUVEAUTÉ : ALGORITHME GLOUTON =====
   budget_max = ...
   def set_cover_glouton(zones, capteurs, budget_max):
       # Initialisation
       zones_restantes = zones.copy()  # Liste des zones à couvrir
       selection = []                  # Liste des capteurs sélectionnés
       cout_total = 0
       fiabilite_totale = 0    
       i_capteur = 0
       while len(zones_restantes) ... and cout_total ... and i_capteur ...:
           capteur = capteurs[i_capteur]
           if ...: # cas d'un non dépassement de budget
               # couverture apportée en plus par ce capteur :
               couverture = ...
               if ...: # cas où le capteur apporte une couverture à une zone non encore couverte
                   selection.append(capteur)
                   zones_restantes = ...    # Retirer les zones couvertes de zones_restantes
                   cout_total = ...
                   fiabilite_totale = ...
           i_capteur += 1
       return {
           "selection": selection,
           "cout_total": cout_total,
           "fiabilite_totale": fiabilite_totale,
           "zones_restantes": zones_restantes,
           "zones_couvertes": difference(zones, zones_restantes)
       }
   
   # ===== EXÉCUTION =====
   resultat = ...
   
   # ===== AFFICHAGE DES RÉSULTATS =====
   print(f"Budget utilisé : {...} € sur les {...} €")
   print(f"Fiabilité totale : {...}%")
   print(f"Ratio de zones couvertes : {...} / {...}")
   
   if ...:
       print(f"Zones non couvertes : {...}")
   else:
       print("Toutes les zones sont couvertes !")
   
   print("\nVoici la liste des capteurs à sélectionner :")
   for capteur in ...:
       print(f"- {capteur['id']}")

6. Exécuter l'algorithme glouton précédent afin de trouver quelle liste de capteurs acheter.

7. Voici une liste d'identifiant de capteurs : ["C9", "C7", "C4", "C6", "C5"].
   Est-ce que cette liste peut convenir ?

8. Que pouvez-vous en conclure quand à cette méthode gloutonne ?